home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 247_01 / brent.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1989-04-17  |  1.8 KB  |  70 lines
  1. /*
  2.  *   Program to factor big numbers using Brent-Pollard method.
  3.  *   See "An Improved Monte Carlo Factorization Algorithm"
  4.  *   by Richard Brent in BIT Vol. 20 1980 pp 176-184
  5.  */
  6.  
  7. #include <stream.hpp>
  8. #include "big.hpp"
  9.  
  10. #define min(a,b) ((a) < (b)? (a) : (b))
  11.  
  12. miracl precision=50;
  13.  
  14. main()
  15. {  /*  factoring program using Brents method */
  16.     long k,r,i,m,iter;
  17.     Big x,y,z,n,q,ys;
  18.     cout << "input number to be factored\n";
  19.     cin >> n;
  20.     if (prime(n))
  21.     {
  22.         printf("this number is prime!\n");
  23.         exit(0);
  24.     }
  25.     m=10;
  26.     r=1;
  27.     iter=0;
  28.     do
  29.     {
  30.         cout << "iterations=" << dec(iter,5);
  31.         q=1;
  32.         do
  33.         {
  34.             x=y;
  35.             for (i=1;i<=r;i++) y=(y*y+3)%n;
  36.             k=0;
  37.             do
  38.             {
  39.                 flushall();
  40.                 iter++;
  41.                 if (iter%10==0) cout << "\b\b\b\b\b" << dec(iter,5);
  42.                 ys=y;
  43.                 for (i=1;i<=min(m,r-k);i++)
  44.                 {   
  45.                     y=(y*y+3)%n;
  46.                     q=((y-x)*q)%n;
  47.                 }
  48.                 z=gcd(q,n);
  49.                 k+=m;
  50.             } while (k<r && z==1);
  51.             r*=2;
  52.         } while (z==1);
  53.         if (z==n) do 
  54.         { /* back-track */
  55.             ys=(ys*ys+3)%n;
  56.             z=gcd(ys-x,n);
  57.         } while (z==1);
  58.         if (!prime(z))
  59.              cout << "\ncomposite factor ";
  60.         else cout << "\nprime factor     ";
  61.         cout << z << "\n";
  62.         if (z==n) exit(0);
  63.         n/=z;
  64.         y%=n;
  65.     } while (!prime(n));      
  66.     cout << "prime factor     ";
  67.     cout << n << "\n";
  68. }
  69.  
  70.